package linkedlist;

import java.util.Random;

/**
 * 给定一个单链表，随机选择链表的一个节点，并返回相应的节点值。
 * 保证每个节点被选的概率一样。
 */
public class no382 {
    ListNode head;
    Random random;
    public no382(ListNode head) {
        this.head = head;
        random = new Random();
    }
    public int getRandom() {
        ListNode cur = head;
        int result = cur.val;
        int index = 1;
        while (cur != null){
            int rand = random.nextInt(index);
            if(rand == 1){
                result = cur.val;
            }
            index++;
            cur = cur.next;
        }
        return result;
    }
}
